#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;


class Solution {
public:
    bool isScramble(string s1, string s2) {
        
        if(s1.size()==1&&s1[0]==s2[0]){
            return true;
        }

        for(int i = 1;i<s1.size();++i){
            //左边的字符串留多少个
            if(func(s1,s2,i)){
                return true;
            }
        }
        return false;
    }
    bool func(string& s1,string& s2, int i){
        string left1(s1.begin(),s1.begin()+i);
        string right1(s1.begin()+i,s1.end());
        string left2(s2.begin(),s2.begin()+i);
        string right2(s2.begin()+i,s2.end());
        string left3 (s2.rbegin(),s2.rbegin()+i);
        string right3(s2.rbegin()+i,s2.rend());
        sort(left1.begin(),left1.end());
        sort(right1.begin(),right1.end());
        sort(left2.begin(),left2.end());
        sort(right2.begin(),right2.end());
        sort(left3.begin(),left3.end());
        sort(right3.begin(),right3.end());
        
        // string temp1 = left1+right1;
        // string temp2 = right1+left1;
        // string temp3 = left2+right2;
        // string temp4 = right2+left2;
        
        if((left1==left2&&right1==right2)||(left1==left3&&right1==right3)){
            return true;
        }
        return false;
    }
};

int main(){
    Solution S;
    cout<<S.isScramble("abcdd","dbdac")<<endl;
}